package me.mingshan.sort;

import java.util.Arrays;

/**
 * 选择排序
 * <p>
 * 核心思想：
 * 每次从未排序数组找到最小的元素，放到数组的前面。
 * <p>
 * 非稳定排序
 */
public class SelectSort {

    public static void main(String[] args) {
        int[] arr = {2,3,2,1,2,5,3,5,7,1,4,6};
        selectSort2(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 选择排序
     * <p>
     * 不稳定实现
     *
     * @param a 待排序数组
     */
    private static void selectSort(int[] a) {
        if (a == null) {
            return;
        }

        for (int i = 0; i < a.length; i++) {
            int min = Integer.MAX_VALUE;
            int minIndex = -1;
            // 找到最小的元素，放到当前i的位置
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < min) {
                    min = a[j];
                    minIndex = j;
                }
            }

            // 发现最小元素，交换位置
            if (minIndex != -1 && a[i] > min) {
                int temp = a[i];
                a[i] = a[minIndex];
                a[minIndex] = temp;
            }
        }
    }


    /**
     * 选择排序
     * <p>
     * 稳定排序， 交换这一步，改变为不交换，整体移动数组
     *
     * @param a 待排序数组
     */
    private static void selectSort2(int[] a) {
        if (a == null) {
            return;
        }

        for (int i = 0; i < a.length; i++) {
            int min = Integer.MAX_VALUE;
            int minIndex = -1;
            // 找到最小的元素，放到当前i的位置
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < min) {
                    min = a[j];
                    minIndex = j;
                }
            }

            // 2,3,2,1

            // 1 2 3 2
            // 1 2 3 2
            // 1 2 2 3
            // 发现最小元素，将i ~ minIndex-1的元素整体移动往后移动一位
            // 然后将i的位置放min的元素
            // 这样不改变元素的相对位置
            if (minIndex != -1 && a[i] > min) {
                for (int k = minIndex - 1; k >= i; k--) {
                    a[k+1] = a[k];
                }

                a[i] = min;
            }
        }
    }
}
